package org.dbrd.util;

import java.util.Comparator;

public class ObjectMinimumPriorityQueue<T> {
	
	private T[] heap;
	
	private int heapSize;
	
	private Comparator<T> comparator;

	public ObjectMinimumPriorityQueue(T[] array, Comparator<T> comparator) {
		if (array.length == 0) {
			throw new RuntimeException("array cannot be of size 0.");
		}
		this.heap = array;
		this.heapSize = array.length;
		this.comparator = comparator;
		this.buildHeap();
	}

	public void add(T value) {
		if (comparator.compare(value, this.heap[0]) > 0) {
			this.heap[0] = value;
			this.minHeapify(0);
		}
	}
	
	public T[] sort() {
		for (int i = this.heapSize - 1; i > 0; i--) {
			swap(i, 0);
			this.heapSize--;
			this.minHeapify(0);
		}
		return this.heap;
	}
	
	private void buildHeap() {
		for (int i = this.lastNonLeafNodeIndex(); i > -1; i--) {
			this.minHeapify(i);
		}
	}
	
	private void minHeapify(int index) {
		if (index >= this.heapSize) {
			throw new RuntimeException("index is out of bounds.");
		}
		int leftIndex = this.leftIndex(index);
		int rightIndex = this.rightIndex(index);
		int smallest = index;
		if (leftIndex < this.heapSize && this.comparator.compare(this.heap[smallest], this.heap[leftIndex]) > 0) {
			smallest = leftIndex;
		}
		if (rightIndex < this.heapSize && this.comparator.compare(this.heap[smallest], this.heap[rightIndex]) > 0) {
			smallest = rightIndex;
		}
		
		if (smallest != index) {
			swap(smallest, index);
			this.minHeapify(smallest);
		}
	}

	private int lastNonLeafNodeIndex() {
		return heapSize / 2 - 1;
	}
	
	private void swap(int index1, int index2) {
		T temp = this.heap[index1];
		this.heap[index1] = this.heap[index2];
		this.heap[index2] = temp;
	}

	private int leftIndex(int index) {
		return index * 2 + 1;
	}

	private int rightIndex(int index) {
		return index * 2 + 2;
	}
}
